package com.andnnl.sum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
 * <p>
 * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 * <p>
 * 示例:
 * <p>
 * 给定 nums = [2, 7, 11, 15], target = 9
 * <p>
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]
 * <p>
 * Created by chenss on 2019/9/23.
 */
public class Sum120Test {
//    static int[] n = { 3, 4, 50, 43, 45, 64, 35, 65};
//    static int[] n = {1, 3, 4, 5, 6, 7, 22, 23, 30, 43, 45, 64, 35, 65};
    static int[] n = {1, 3, 4, 5, 6, 7, 22,2,55,44,1, 3, 4, 5, 6, 7, 22,2,55,44,66,77,43,111,333,555,444,335,732,123,421,1234,5234,1234,32};
    static List<Integer> list = new ArrayList<>();
    static long count=0;
    public static void main(String[] args) {
//        Arrays.sort(n);
        System.out.println(n);
        int sum = 12000;
        int rs = cal(sum, n.length - 1);
//        System.out.println("rs:" + Arrays.sort.stream().mapToInt(Integer::intValue).sum());
        if (rs == 0)
            System.out.println("rs:" + list.stream().mapToInt(Integer::intValue).sum() + " " + list);
        else {
            System.out.println("无解");
        }
    }

    private static int cal(int sum, int idx) {
        if (idx == 0) return -1;
        for (int k = idx; k >= 0; k--) {
            count++;
            if(count%100000000==0){
                System.out.println(count);
            }
            int x = sum - n[k];
            if(x==0){
                list.add( n[k]);
                return 0;
            }
            if(x<0){
                continue;
            }
            int rs = cal(x, k - 1);
            if(rs==0){
                list.add( n[k]);
                return 0;
            }
        }
        return -1;
    }


}
